package com.origin.niuke.dynamic;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/27 21:20
 * 最长公共子串
 * 给定两个字符串str1和str2,输出两个字符串的最长公共子串
 * 题目保证str1和str2的最长公共子串存在且唯一。
 * 算法：动态规划
 * dp[i][j]: 表示 str1 下标为 i 结尾和 str2 下标为 j 结尾时，最长的公共子串
 */
public class NC127 {

    public String LCS (String str1, String str2) {
        int n = str1.length(), m = str2.length(), maxLastIdx = 0, maxLen = 0;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    maxLastIdx = j - 1;
                }
            }
        }
        return str2.substring(maxLastIdx - maxLen + 1, maxLastIdx + 1);
    }

}
